\magnification = 2200 %\magstep3

\def\UseTimesRoman{
\font\cmr=Times
\font\TR=Times at 10pt
\font\TRXII=Times at 12pt
\font\TRXIV=Times at 14pt
\font\TRXX=Times at 20pt
\font\TRXXIV=Times at 24pt
\font\TI=TimesI at 10pt     %Times Italic
\font\TB=TimesB at 10pt     %Times Bold
\font\TBI=TimesBI at 10pt   %Times Bold Italic
\font\TBIviii=TimesBI at 8pt
\font\TBIv=TimesBI at 5pt
%\font\TO=TimesO at 10pt  %Times Oblique (Times Roman, slanted 22%
  %    with EdMetrics)
\font\TO=TimesI at 10pt  %Times Oblique (Times Roman, slanted 22% with EdMetrics)

\font\TIVIII=TimesI at 8pt
\font\TRVIII=Times at 8pt
\font\TIVI=TimesI at 6pt
\font\TRVI=Times at 6pt

	     \font\tenrmscld=Times at 10 pt
        \font\sevenrmscld=Times at 7 pt
        \font\fivermscld=Times at 5 pt

        \font\teniscld=cmmi10 at 10.3 pt
        \font\seveniscld=cmmi10 at 7.21 pt
        \font\fiveiscld=cmmi10 at 5.15 pt
        \font\tensyscld=cmsy10 at 10.3 pt
        \font\sevensyscld=cmsy10 at 7.21 pt
        \font\fivesyscld=cmsy10 at 5.15 pt
        \font\tenexscld=cmex10 at 10.3 pt
        \font\tenbfscld=cmbx10 at 10.3 pt
        \font\sevenbfscld=cmbx10 at 7.21 pt
        \font\fivebfscld=cmbx10 at 5.15 pt

\font\Courier = Courier
\font\Symbol = Symbol

\def\Omega{\hbox{{\Symbol W}}}

\textfont0=\tenrmscld \scriptfont0=\sevenrmscld\scriptscriptfont0=\fivermscld
\def\rm{\fam0\tenrmscld}
\textfont1=\teniscld \scriptfont1=\seveniscld \scriptscriptfont1=\fiveiscld
\def\mit{\fam1} \def\oldstyle{\fam1\teni}
\textfont2=\tensyscld \scriptfont2=\sevensyscld \scriptscriptfont2=\fivesyscld
\def\cal{\fam2}
\textfont3=\tenexscld \scriptfont3=\tenexscld \scriptscriptfont3=\tenexscld
\def\it{\TI}
\def\sl{\TO}
\def\bf{\TB}
\def\rm{\TR}
%\def\tt{\ttCourier}
\def\tt{\Courier}
\def\abstractfont{\TRVIII}
\def\footnotefont{\TRVIII}
\def\tinyfont{\TRvi}
\def\smalltitlefont{\TRXII}
\def\titlefont{\TRXIV}
\def\bigtitlefont{\TRXX}
\def\verybigtitlefont{\TRXXIV}
\textfont9=\TBI \scriptfont9=\TBIviii \scriptscriptfont9=\TBIv
\def\mbi{\fam9}
\rm
        }

%\UseTimesRoman

\def\BR{\Bbb R}             % Besondere Buchstaben
\def\BC{\Bbb C}
\def\BI{\Bbb I}
\def\BN{\Bbb N}
\def\BQ{\Bbb Q}
\def\BS{\Bbb S}
\def\BZ{\Bbb Z}
\def\Tilde{$_{\hbox{\cmrXX \~{}}}$}
\def\ST{\hbox{\eu T }}
\def\SRS{\hbox{\eu RS}}
\def\i{\hbox{{\bf i}}}

\font\sc=cmcsc10 at 10 pt   %% or: at 10 pt
\font\eu=eusb10 %at 10 pt
\font\small=cmr8 at 8 pt
\font\cmrX=cmbx10 scaled \magstep 1 %% 12 point CM
\font\cmrXX=cmbx12 scaled \magstep 1 %%

\hsize 7 true in
\vsize 9.25 true in
\hoffset = -0.20 true in
\voffset -0.25 true in
\parskip=3pt

\overfullrule = 0pt



\input amssym.def            % small letters for UNIX,  not: AMSsym.def
\input epsf.def% \input epsf %for UNIX
%\input epsf          %\input epsf.def for MAC f"ur BILDER!!
\input pics.tex

\input BoxedEPS
\SetTexturesEPSFSpecial
\HideDisplacementBoxes

\def\lf{\ \hfil\break}       % Neue Zeile ohne Einr"ucken, 'linefeed'
\def\cl{\centerline}
\def\Lf{\vskip1pt\noindent}   % Neue Zeile mit breiterem Zwischenraum
\def\LF{\medskip\noindent}   % Neue Zeile mit breiterem Zwischenraum
\def\R90{{\rm Rot}(90^\circ)}
\def\Dd#1{{\partial \over \partial #1}}

\nopagenumbers

\vglue -10pt
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\cl {\cmrX  About  Hilbert's Square Filling Curve }
\lf
\cl { See also: Koch Snowflake, Dragon Curve  }
\cl {Speed up demos by pressing DELETE  }

\lf
In 1890---the year the German Mathematical Society was founded,  David 
Hilbert published a construction of a continuous curve whose image
completely fills a square. At the time, this was a contribution to the understanding
of continuity, a notion that had become important for Analysis in the second
half of the 19th century. Today, Hilbert's curve has become well-known
for a very different reason---every computer science student learns about it
because the algorithm has proved useful in image compression.
In this application one has to enumerate a first square, its four half size
subsquares, their sixteen quarter-size subsquares and so on, in such a way
that squares whose numbers are close are also close to each other geometrically.
In other words, the continuity of this space filling curve is now important, in contrast
to the fact that the curve was considered a pathological example of continuity for
many years after Hilbert's discovery.
\Lf
It was known in 1890 that such a curve, i.e., a continuous map $c$ of $[0,1]$ onto
$[0,1]\times[0,1]$, could not be one-to-one, i.e., 
{\it Certain pairs of points $t_1,t_2$ of the interval $[0,1]$ must have
the same image $c(t_1)=c(t_2)\in [0,1]\times[0,1]$. }
This led Hilbert to give a special twist to his construction: He gave a sequence of
polygon approximations of the strange limit curve that, surprisingly, were all one-to-one!
In retrospect it seems almost as if Hilbert foresaw what would be needed a century later in image compression; when people say that they are using Hilbert's square-filling curve, 
they mean more precisely that they are using Hilbert's approximations to that curve!
\Lf
The basis of Hilbert's construction is a single step that is repeated over and over
again.  We first explain a simplified version, although this does not exactly give Hilbert's
one-to-one approximations that made the construction so famous.
Assume that we already have a curve inside the square and joining the left bottom 
corner to the right bottom corner. 3DXM offers four different initial such curves, 
 leading to quite different pictures. The basic construction step is to scale the square and
its curve by $1\over 2$ and put {\bf four} copies of this smaller square side by side in the
original square, in such a way that these four smaller copies of the curve fit
together to form a new curve from the left bottom corner to the right bottom corner of 
the original square.  But instead of reading more words, we suggest that you view 
the default approximations of the Hilbert curve in 3DXM. We use a rainbow coloration
to emphasize the continuous parametrization, and we repeat the colors {\bf four} times to
emphasize that four copies of the previous approximation make up the new one.
 \lf
The two end points of the curve (to which this basic iteration step is applied) play a special
role, on the one hand they lead at each iteration step to more points that are already
points on the limit curve, on the other hand exactly these easy points lead to double points
on the approximations! Hilbert therefore removed small portions of the curve near its two
end points before he applied the above iteration step. 
One can see how these Hilbert approximations manage to stay one-to-one and how they 
wander through all the little squares of the current subdivision of the original square---and 
these  are just the properties used in image compression. 
\lf
In 3DXM one can choose with the parameter cc between several initial curves. An even
number and the following odd number choose the same curve, but for even cc the Hilbert
iteration is done {\it without} the endpoints and for odd cc {\it including} the endpoints. In the
Action Menu one can switch between Hilbert's approximation (cc=0) and one that 
emphasizes the iteration of the endpoints (cc=5).
\Lf
Finally we add to the above descriptive part some more technical explanations, namely
how to understand the limit as a continuous curve. Select the Action Menu
entry ``Emphasize Limit Points''. The first shown step (for our default value cc = 5) is a curve 
that is mostly a straight  segment, but has also two little wiggles, that emphasize the initial 
point $c(0)$ and the end point $c(1)$. 
The second step is a curve with four straight segments that join five
wiggles, the points $c(j/4),\ j:=0,\dots,4$. These points are really points on the limit curve
because they remain fixed under all further applications of Hilbert's basic construction
step. In the third step we get 17 wiggles, the points $c(j/16),\ j:=0,\dots,16$ of the limit
curve, and so on. The 3DXM demo shows six such iterations. One can deduce from this
the continuity of the limit curve if one proves for these approximations:\lf
$$|t_2-t_1| \le {1\over 4^n}  \Rightarrow |c(t_2) - c(t_1)| \le {1\over 2^n}.$$

\Lf

\bye
 

 